정점에 의 번호가 붙은 트리 이 주어진다.
같은 정점들을 가지는 두 트리 에 대해, 다음을 만족하는 정점들의 집합 가 존재하지 않을 때 과 는 에 있다고 하자.
유도 부분 그래프의 정의
그래프에서 정점들의 집합 가 유도하는 부분 그래프란, 에 속한 정점과 양 끝점이 모두 에 속하는 간선만을 남겨 얻는 그래프이다.
과 좋은 관계에 있는 트리 가 존재하는지 판정하고, 존재한다면 하나를 구성하라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 다음과 같이 출력한다.
조건을 만족하는 가 존재하지 않으면 한 줄에 을 출력한다.
존재한다면 개의 줄에 걸쳐 다음과 같이 출력한다.
각 테스트 케이스는 다음과 같은 형식으로 주어진다.
의 번 간선은 정점 와 를 잇는다.
출력한 개의 간선 은 정점 으로 이루어진 트리 를 이루어야 하며, 과 는 좋은 관계여야 한다.
가능한 답이 여러 가지라면 아무거나 출력해도 된다.
| 4 | 48 | 추가적인 제약이 없다. |
