Valar Morghulis
시간 제한2초메모리 제한512 MB
라이벌 관계 그래프가 주어질 때, 각 질의에 해당하는 간선 구간만 사용한 그래프가 이분 그래프인지 판정하고, 가능하면 한쪽 날개의 최대 크기를 출력한다.
문제
Khaleesi가 Kings Landing을 향해 출항했다. 세 마리의 드래곤과 수만 명의 군대를 거느린 그녀는 막을 수 없다. 배가 Kings Landing에 가까워지고 있고, 그녀는 공격 계획을 세우려 한다.
공격 계획은 군대를 오른쪽과 왼쪽 두 날개로 나누는 것이다. 문제가 하나 있다. Khaleesi의 병사들은 출신이 매우 다양하고, 일부는 서로 적대 관계여서 함께 있을 수 없다(예를 들어 Martell과 Tyrell). 따라서 그런 병사들은 같은 날개에 있을 수 없다.
Khaleesi는 모든 적대 관계를 알고 있고, 그중 일부를 해결하려 할 수 있다. 그러나 해결하기 어려운 적대 관계도 있어 그대로 감수해야 한다. 그녀는 일부 적대 관계가 해결되지 않은 상태에서, 서로 함께 있을 수 없는 두 병사가 같은 날개에 속하지 않도록 군대를 두 날개로 나눌 수 있는지 확인하려 한다. Khaleesi가 철왕좌에 앉기 위한 공격 계획을 세우도록 도와줄 수 있는가?
입력
프로그램은 하나 이상의 테스트 케이스로 검사된다. 입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다(1 ≤ T ≤ 10).
각 테스트 케이스는 세 개의 정수가 공백으로 구분되어 있는 한 줄로 시작한다.
- N: 병사의 수(1 ≤ N ≤ 40,000)
- E: 적대 관계의 수(1 ≤ E ≤ 40,000)
- Q: 질의의 수(1 ≤ Q ≤ 40,000)
이어서 E개의 줄이 주어지며, 각 줄에는 두 정수 A와 B가 공백으로 구분되어 있다. 이는 병사 A와 B가 같은 날개에 있을 수 없음을 뜻한다(1 ≤ A, B ≤ N).
이어서 Q개의 줄이 주어지며, 각 줄에는 두 정수 C와 D가 공백으로 구분되어 있다. 이는 [C, D] 범위의 모든 적대 관계를 해결할 수 없음을 뜻한다(1 ≤ C, D ≤ E).
출력
각 테스트 케이스마다 Q개의 줄을 출력한다. i번째 줄은 i번째 질의의 답이다. 군대를 두 날개로 나눌 수 없으면 ‘-1 -1’을 출력하고, 그렇지 않으면 두 날개의 크기를 공백 하나로 구분하여 출력한다. 유효한 배치가 여러 개라면 첫 번째 날개의 크기가 최대가 되는 배치를 출력한다.