Rikka with Linker

커맨드 라인에서 C++ 프로젝트를 컴파일해 본 적이 있다면 링커에 익숙할 것이다. 두 정적 라이브러리 liba.a와 libb.a를 사용하는데 liba.a가 libb.a에 의존한다면, 커맨드에서 liba.a를 libb.a보다 앞에 두어야 한다. 예를 들어 "g++ -o my my.cpp liba.a libb.a"처럼 쓴다.

liba.a와 libb.a가 서로 의존한다면 어떻게 될까? "g++ -o my my.cpp liba.a libb.a liba.a"처럼 두 이름을 커맨드에 여러 번 넣어야 한다. 형식적으로, 두 라이브러리 liba.a와 libb.a를 사용하는데 liba.a가 libb.a에 의존한다면, 커맨드에서 어떤 libb.a보다 앞에 오는 liba.a가 적어도 하나 있어야 한다.

이제 Rikka는 자신의 C++ 프로젝트를 진행 중이고, 사용할 정적 라이브러리가 $n$개 있다. 의존 관계는 $m$쌍이다. 쌍 $(i, j)$는 $i$번째 라이브러리가 $j$번째 라이브러리에 의존한다는 뜻이다.

복잡한 커맨드는 행복을 가져다주지 않는다. 그래서 Rikka는 컴파일 커맨드를 단순하게 만들고 싶다. 구체적으로, 컴파일 커맨드에 들어가는 정적 라이브러리 이름의 개수를 가능한 한 작게 만들고 싶다. 이 개수를 구해 주자.

첫 번째 줄에 정수 $t$ ($1 \leq t \leq 10^3$)가 주어진다. 이는 테스트 케이스의 수이다.

각 테스트 케이스의 첫 번째 줄에 두 정수 $n$과 $m$ ($1 \leq n \leq 18$, $0 \leq m \leq n \cdot (n-1)$)이 주어진다.

이어서 $m$개의 줄이 주어지고, 각 줄에 두 정수 $a$와 $b$ ($1 \leq a, b \leq n$, $a \neq b$)가 주어지며 의존 관계를 나타낸다. 라이브러리 $a$가 라이브러리 $b$에 의존한다는 뜻이다.

각 의존 관계는 최대 한 번만 주어지며, $n > 12$인 테스트 케이스는 최대 $20$개이다.

각 테스트 케이스마다 Rikka의 컴파일 커맨드에 들어가는 라이브러리 이름 개수의 최솟값을 한 줄에 하나씩 출력한다.