해파리

우리 Jagiellonian 대학교가 식물을 매우 사랑한다는 것은 모두가 안다. 우리는 나무, 숲, 심지어 선인장에 관한 문제도 수백 개 만들었다. 안타깝게도 동물에 관한 문제는 그다지 인기가 없다. 오늘은 우리가 동물도 똑같이 사랑한다는 것을 증명하려 한다.

정점의 개수와 간선의 개수가 같은 단순 연결 무방향 그래프를 해파리(jellyfish)라고 한다. 정점이 $n$개인 해파리 $J$가 주어진다. 정점 집합의 부분집합 $S \subseteq J$에 대해, 모든 $T \subseteq S$마다 $T$의 모든 정점을 포함하고 $S$의 다른 정점은 포함하지 않는 연결된 부분그래프가 존재하면, $S$를 멋진 부분집합(awesome subset)이라고 한다.

$J$의 멋진 부분집합 중 가능한 최대 크기는 얼마인가?

첫 줄에 테스트 케이스의 개수 $z$가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 해파리의 정점 개수 $n$ ($3 \leq n \leq 100\,000$)이 한 정수로 주어진다.

다음 $n$개의 줄에는 해파리의 간선을 나타내는 두 정수 $u_i$, $v_i$ ($1 \leq u_i \neq v_i \leq n$)가 한 줄에 하나씩 주어진다. 주어지는 그래프는 해파리가 보장되며, 두 정점 사이에 간선은 최대 하나만 있다.

모든 테스트 케이스의 정점 수 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 해파리의 멋진 부분집합 중 최대 크기를 나타내는 정수 하나를 한 줄에 출력한다.