시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1050 | 229 | 124 | 20.228% |
N개의 도시와, 서로 다른 두 도시를 잇는 E개의 도로로 이루어진 나라가 있다. 각 도시는 1번부터 N번까지 번호가 매겨져 있으며, 도로는 양방 통행 도로이다. 즉 i번 도시와 j번 도시 사이에 도로가 존재한다면 i번 도시에서 j번 도시로 이동할 수 있을 뿐더러 j번 도시에서 i번 도시로도 이동할 수 있다.
이 나라의 교통 체계는 매우 복잡해서, 이를 간소화하는 작업을 벌이려고 한다. 간소화를 위한 방법으로는 크게 두 가지가 있다. 두 도시를 연결하는 특정한 도로를 골라서 없애는 단순한 방법이 있고, 특정한 도시를 골라서 이 도시로 들어오거나 나가는 모든 도로를 없애는 방법이 있다.
이러한 교통 체계의 단순화는 면밀한 검토가 필요한 복잡한 작업이 된다. 따라서 몇 개의 질문을 만들어 놓고, 이 질문들에 대한 답을 구해낸 후 이를 토대로 단순화 작업을 벌이기로 하였다. 질문의 유형은 아래의 두 가지 중 하나를 따른다.
이 나라의 현재 교통 체계에 대한 정보와 위의 유형에 해당되는 여러 개의 질문들이 주어졌을 때, 교통 체계의 단순화를 위해 주어진 질문들에 대한 답을 구하는 프로그램을 작성하시오.
첫째 줄에 도시의 개수 N과 도로의 개수 E가 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ E ≤ 500,000) 이어서 E개의 줄에 걸쳐 각 줄에 N 이하의 서로 다른 두 자연수가 주어지는데, 이는 두 자연수를 번호로 하는 두 개의 도시 사이에 도로가 존재함을 의미한다. 같은 도로가 여러 번 입력으로 주어지지 않으며, 임의의 두 도시 사이에 항상 이동할 수 있는 경로가 하나 이상 존재하는 교통 체계만이 입력으로 주어진다.
다음 줄에는 질문의 개수 Q가 주어진다. (1 ≤ Q ≤ 300,000) 이어서 Q개의 줄에 걸쳐 질문에 대한 정보가 주어지는데, 각 줄의 첫 번째 자연수는 질문의 유형을 나타내는 1 또는 2이다. 질문이 유형 1에 해당하는 경우는 N 이하의 네 개의 자연수 A, B, G1, G2가 순서대로 주어진다. A와 B는 서로 다르며, G1과 G2 사이에 항상 도로가 존재하는 경우만이 입력으로 주어진다. 질문이 유형 2에 해당하는 경우는 N 이하의 서로 다른 자연수 A, B, C가 순서대로 주어진다.
Q개의 줄에 걸쳐 각 질문에 대한 답을 한 줄에 하나씩 yes나 no로 출력한다. 질문의 답이 "이동할 수 있다"이면 yes를, "이동할 수 없다"이면 no를 출력하면 된다.
13 15 1 2 2 3 3 5 2 4 4 6 2 6 1 4 1 7 7 8 7 9 7 10 8 11 8 12 9 12 12 13 5 1 5 13 1 2 1 6 2 1 4 1 13 6 7 8 2 13 6 7 2 13 6 8
yes yes yes no yes
Olympiad > Croatian Highschool Competitions in Informatics > 2007 > Croatian Olympiad in Informatics 2007 2번