# Untitled

unknown
plain_text
a year ago
1.3 kB
0
Indexable
Never
```import java.util.Scanner;

public class Solution {
static int N,M,u,v,f,r,ans;
static int[][] ke,vs;
static int[] len,q,d;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
for (int t = 1; t <= tc; t++) {
N = sc.nextInt();
M = sc.nextInt();
ke = new int[N+1][N+1];
len = new int[N+1];
for(int i=0;i<M;i++){
int x = sc.nextInt();
int y = sc.nextInt();
ke[x][len[x]++] = y;
}
vs = new int[2][N+1];
ans = Integer.MAX_VALUE;
vs[0][1] = 1;
DFS(1,0);
System.out.println(ans);
}
}
static void DFS(int u, int k){
if(u==1&&vs[1][u]==1){
ans = Math.min(ans, count());
return;
}
if(count()>=ans) return;
for(int i=0;i<len[u];i++){
if(vs[k][ke[u][i]]==0){
if(ke[u][i]==2){
vs[k][ke[u][i]]=1;
vs[k+1][ke[u][i]]=1;
DFS(ke[u][i],k+1);
vs[k][ke[u][i]]=0;
vs[k+1][ke[u][i]]=0;
}
else {
vs[k][ke[u][i]]=1;
DFS(ke[u][i],k);
vs[k][ke[u][i]]=0;
}
}
}
}
static int count(){
int tmp = 0;
for(int i=1;i<=N;i++){
if(vs[0][i]!=0||vs[1][i]!=0) tmp++;
}
return tmp;
}
}
```