메뉴 건너뛰기

문제

00b53 변형된 바이러스 3  

시간메모리제출 올바른 답 비율
1초64MB
156
20
12.8%


나의 횟수나의 최근 판정시도 성공 비율
1916
84.2%
변형된 바이러스 

인터넷 상에 새로운 바이러스가 유포되고 있다. 이 바이러스는 다른 컴퓨터를 감염시킬 때마다 변형되고 있어 백신을 만들기가 매우 어려워 고민이다. 하지만 다행스러운 점은 이 바이러스는 자신과 같은 타입의 바이러스에 대한 정보를 가지고 있다. 임의로 바이러스를 숫자를 붙여 표현한다면,

▪ 1번 바이러스는 2번 바이러스와 같은 타입

▪ 2번 바이러스는 3번 바이러스와 같은 타입

▪ 4번 바이러스는 5번 바이러스와 같은 타입 이라고 가정하자.

그렇다면 1번 바이러스와 3번 바이러스는 같은 타입이라고 할 수 있다. 하지만 1번 바이러스와 5번 바이러스는 다른 타입의 바이러스이다. 발견된 바이러스의 정보를 통해서 특정 바이러스 A, B 가 같은 타입의 바이러스인지 확인해 보자.

입력

첫째 줄에 바이러스 개수 N(1≤N≤1,000,000)과 바이러스의 관계 K개(1≤K≤1,000,000)이 입력된다. 

둘째 줄부터 K개의 줄에는 바이러스의 관계가 자신의 바이러스 번호 I, 자신의 바이러스와 같은 타입의 번호 J라 할때, I J의 형태로 주어진다.

K+2번째 줄에는 문항의 개수 Q가 입력되며, 그 다음 줄부터 바이러스 번호A, B가 Q개 주어진다.

출력

A B 가 같은 타입의 바이러스라면 1을 아니라면 0을 출력한다.

예시
1입력
3 2
1 2
2 3
3
1 2
2 3
1 3
출력
1
1
1
출처
2017년 충북 정보올림피아드 지역예선 고등부 3번
위로