모든 간선을 한 번씩

정점이 $N$개이고 간선이 $M$개인 그래프가 주어진다. 정점의 번호는 $0$부터 $N-1$까지이다. 그래프는 방향 그래프 또는 무방향 그래프이며, 자기 루프와 중복 간선이 있을 수 있다.

모든 간선을 정확히 한 번씩 지나는 경로가 존재하는지 판별해 보자. 시작 정점 $S$가 지정되어 있다면 $S$에서 출발해야 하며, $S=-1$이면 어느 정점에서든 출발할 수 있다. 간선이 없을 때는 정점 하나만 지나는 경로도 허용한다.

첫 번째 줄에 테스트 케이스의 수를 의미하는 정수 $Q$가 주어진다. $(1 \le Q \le 100)$

각 테스트 케이스의 첫 번째 줄에 그래프의 종류를 의미하는 정수 $D$, 두 정수 $N$, $M$과 시작 정점 번호 $S$가 공백으로 구분되어 주어진다. $(0 \le D \le 1; 1 \le N \le 100\,000; 0 \le M \le 200\,000; -1 \le S < N)$ $D=0$이면 무방향 그래프, $D=1$이면 방향 그래프이다.

두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 양 끝 정점 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(0 \le u, v < N)$ 방향 그래프에서는 $u$에서 $v$로 향하는 간선이다.

전체 테스트 케이스에서 $N$의 합은 $200\,000$ 이하이고 $M$의 합은 $300\,000$ 이하이다.

각 테스트 케이스마다 조건을 만족하는 경로가 있다면 $1$을, 그렇지 않다면 $0$을 한 줄에 출력한다.