두 작업장에 나누기
문제
공장에는 작업장이 두 곳 있다. 작업자는 V명이고 1번부터 V번까지 번호가 붙어 있다. 모든 작업자는 두 작업장 가운데 한 곳에 반드시 배치된다. 한 작업장에 몇 명이 들어가는지는 상관이 없으며, 한 곳이 비어도 된다.
그런데 작업자 중에는 손발이 맞지 않아 같은 작업장에 함께 둘 수 없는 쌍이 있다. 그런 쌍이 M개 주어진다. 각 쌍은 양쪽 모두에 해당하는 관계라서, A번과 B번이 한 쌍이라면 A번의 입장에서도 B번의 입장에서도 같은 작업장에 있을 수 없다. 두 사람이 서로 다른 작업장에 있으면 그 쌍은 지켜진 것이다.
주어진 M개의 쌍을 하나도 어기지 않도록 V명 전원을 두 작업장에 배치할 수 있는지 판정하는 프로그램을 작성하여라. 공장 여러 곳에 대한 정보가 차례대로 주어지므로 각 공장마다 판정해야 한다.
예를 들어 작업자가 V=3명이고, 함께 둘 수 없는 쌍이 M=2개로 다음의 표와 같다고 해보자.
| 쌍 | 1 | 2 |
|---|---|---|
| 함께 둘 수 없는 두 사람 | 2번과 3번 | 2번과 1번 |
이 경우 다음과 같이 배치하면 두 쌍을 모두 지킬 수 있다.
| 작업장 | 첫 번째 | 두 번째 |
|---|---|---|
| 배치한 작업자 | 2번 | 1번, 3번 |
1번과 3번은 함께 둘 수 없는 쌍이 아니므로 같은 작업장에 있어도 된다. 따라서 이 경우에는 배치할 수 있다.
반면에 작업자가 V=4명이고, 함께 둘 수 없는 쌍이 M=4개로 다음의 표와 같다고 해보자.
| 쌍 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 함께 둘 수 없는 두 사람 | 2번과 4번 | 2번과 3번 | 4번과 3번 | 1번과 4번 |
이 경우 2번과 3번과 4번 세 사람은 서로가 모두 함께 둘 수 없는 쌍을 이룬다. 작업장은 두 곳뿐이므로 세 사람을 어떻게 나누어 넣어도 적어도 두 사람이 같은 작업장에 들어가고, 그 두 사람은 쌍을 어기게 된다. 따라서 이 경우에는 배치할 수 없다.
입출력 예시
예시 1
입력
1 3 2 2 3 2 1
출력
YES
예시 2
입력
1 4 4 2 4 2 3 4 3 1 4
출력
NO
예시 3
입력
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2
출력
YES NO
입력 조건
가장 먼저 공장의 수 T가 자연수로 주어진다. T는 1 이상 5 이하의 자연수다.
이어서 T개의 공장에 대한 정보가 차례대로 주어진다. 각 공장의 정보는 먼저 한 줄에 작업자의 수 V와 함께 둘 수 없는 쌍의 수 M이 공백으로 구분되어 주어진다. V는 2 이상 20,000 이하의 자연수이며, M은 1 이상 200,000 이하의 자연수다.
이어서 M개의 줄에 걸쳐 각 쌍의 두 작업자 번호가 공백으로 구분되어 주어진다. 두 번호는 모두 1 이상 V 이하의 자연수이며 서로 다르다. 같은 쌍이 두 번 주어지는 경우는 없다.
출력 조건
각 공장마다 전원을 두 작업장에 배치할 수 있다면 "YES"를, 배치할 수 없다면 "NO"를 한 줄에 하나씩 차례대로 출력한다. 두 글자 모두 대문자로 출력한다.
요구사항
- 모든 작업자를 두 작업장 가운데 한 곳에 반드시 배치합니다
- 한 작업장이 비어도 되고, 두 작업장의 인원이 달라도 됩니다
- 함께 둘 수 없는 쌍의 두 사람은 서로 다른 작업장에 있어야 합니다
- 공장마다 "YES" 또는 "NO"를 한 줄에 하나씩 차례대로 출력합니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
1 3 2 2 3 2 1
YES
1 4 4 2 4 2 3 4 3 1 4
NO
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2
YES NO
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.