RiseOJ – 팔찌 교차

설명

소 베시는 미술과 공예를 즐긴다. 여가 시간에 베시는 $$N$$ 개( $1\le N\le 50$ )의 팔찌를 만들었고, 편의상 $1 \ldots N$ 으로 번호를 붙였다. $$i$$ 번째 팔찌는 $$N$$ 가지 서로 다른 색 중 색 $$i$$ 로 칠해져 있다. 팔찌를 만든 후, 베시는 전시를 위해 팔찌들을 테이블(2차원 평면으로 생각할 수 있다) 위에 올려놓았다. 베시는 다음 세 가지 조건을 만족하도록 팔찌를 조심스럽게 배치했다.

모든 팔찌는 하나의 닫힌 다각형 사슬(polygonal chain)이었다. 즉, 일련의 꼭짓점(점)들이 선분으로 순서대로 연결되어 있고 첫 점과 마지막 점이 같다(자세한 내용은 위키백과 문서를 참고하라: polygonal chain),
어떤 팔찌도 자기 자신과 교차하지 않았다(이는 "단순(simple)" 다각형 사슬에 해당한다); 그리고
어떤 두 팔찌도 서로 교차하지 않았다.

안타깝게도, 베시가 이렇게 조심스럽게 팔찌를 배치한 직후 농부 존이 트랙터를 몰고 지나가면서 테이블이 흔들렸고, 팔찌들이 움직여 여러 개의(반드시 닫혀 있거나 단순하지는 않은) 다각형 사슬로 부서졌을 수도 있다! 그 후 베시는 위의 세 조건이 여전히 성립하는지 확인하고 싶었다. 하지만 날이 어두워서 팔찌를 더 이상 볼 수 없었다.

다행히 베시에게는 손전등이 있었다. 베시는 $$M$$ 개( $1\le M\le 50$ )의 수직선 $x=1, x=2, \ldots, x=M$ 을 선택하고, 각 수직선을 따라 손전등 빛을 $y=-\infty$ 부터 $y=\infty$ 까지 훑으면서 보이는 모든 팔찌의 색을 나타난 순서대로 기록했다. 다행히 어떤 빛도 다각형 사슬의 꼭짓점이나 두 선분을 동시에 지나가지 않았다. 또한 각 빛에 대해, 나타난 모든 색은 정확히 두 번씩 나타났다.

이 정보를 이용해 팔찌들이 여전히 위의 세 조건을 모두 만족하는 것이 가능한지 판별하도록 베시를 도와줄 수 있는가?

출제자: Richard Qi

제약

배점

테스트 케이스 2는 $$N = 1$$ 을 만족한다.
테스트 케이스 3-5는 $$N=2$$ 를 만족한다.
테스트 케이스 6-8은 $$M=1$$ 을 만족한다.
테스트 케이스 9-14는 $$M=2$$ 를 만족한다.
테스트 케이스 15-20은 추가 제약이 없다.

출제자: Richard Qi

입력 형식

각 입력 케이스는 $$T$$ 개( $1 \leq T \leq 50$ )의 서브 케이스를 포함하며, 전체 입력 케이스를 해결하려면 모든 서브 케이스를 독립적으로 해결해야 한다. 연속한 테스트 케이스는 개행으로 구분된다.

입력의 첫째 줄에 $$T$$ 가 주어진다. 이어서 $$T$$ 개의 서브 테스트 케이스가 주어진다.

각 서브 테스트 케이스의 첫째 줄에 두 정수 $$N$$ 과 $$M$$ 이 주어진다. 이어서 각 서브 테스트 케이스는 $$M$$ 개의 추가 줄을 포함한다. $$1$$ 부터 $$M$$ 까지의 각 $$i$$ 에 대해, $$i$$ 번째 추가 줄에는 정수 $$k_i$$ ( $0\le k_i\le 2N$ , $$k_i$$ 는 짝수)와 그 뒤에 $$k_i$$ 개의 정수 $c_{i1}, c_{i2},\ldots, c_{ik_i}$ ( $c_{ij}\in [1,N]$ , 모든 $c_{ij}$ 는 0번 또는 2번 등장)가 주어진다. 이는 베시가 손전등을 $(i,-\infty)$ 에서 $(i,\infty)$ 로 훑었을 때 색 $c_{i1}, c_{i2},\ldots, c_{ik_i}$ 를 이 순서대로 만났다는 뜻이다.

출력 형식

각 서브 테스트 케이스에 대해, 위의 세 조건이 만족될 수 있으면 YES를 출력한다. 그렇지 않으면 NO를 출력한다.

예제 1

입력

5

1 2
2 1 1
2 1 1

1 3
2 1 1
0
2 1 1

2 1
4 1 2 1 2

4 2
6 1 2 2 3 3 1
6 1 2 4 4 2 1

2 2
4 1 1 2 2
4 2 2 1 1

출력

YES
NO
NO
YES
NO

설명

An example of a feasible bracelet configuration for the first sub-case is:

For the fourth sub-case, a feasible arrangement is the following:

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > December > Gold

올림피아드 > USACO > 2021-2022 > December > Gold

태그

JudgeUSACO

팔찌 교차

평가 및 의견

풀이 제출