ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#10897

고양이 몰기 2s 2048MB

問題

바쿠에 고양이 카페를 열고, 창가에 앉아 있는 고양이들의 홍보 사진을 찍고 싶다. 하지만 고양이가 원하는 대로 움직이게 하는 것은 유명하게도 어려운 일이다. 그래도 계획이 있다. 종류가 모두 다른 m개의 개박하 식물을 샀고, 각 고양이는 이 중 일부 종류를 좋아한다. 창가에는 1부터 m까지 번호가 붙은 m개의 화분이 일렬로 놓여 있으며, 각 화분에 식물을 하나씩 놓을 것이다. 각 고양이는 (실에 달린 장난감을 이용해) 화분 1번부터 m번까지 줄을 따라 걷게 된다. 고양이는 자신이 좋아하는 개박하가 있는 화분에 도달하는 즉시 그곳에 멈추며, 그 화분에 이미 다른 고양이가 있어도 상관하지 않는다.

그림 F.1: 첫 번째 예제에 대한 가능한 식물 배치 중 하나.

각 고양이가 어느 화분에 멈추길 원하는지 알고 있다. 원하는 대로 식물을 배치할 수 있는가?


入力

첫 줄에는 테스트 케이스 수 t(1 ≤ t ≤ 10\, 000)가 주어진다. 이어서 t개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 고양이 수 n과 개박하 식물 수(화분 수) m이 주어진다(1 ≤ n ≤ 2 \cdot 10^5, 1 ≤ m ≤ 2 \cdot 10^5). 개박하 식물은 1부터 m까지 번호가 매겨져 있다.

다음 n줄은 각 고양이를 설명한다. 각 줄은 두 정수 p, k로 시작하며, p(1 ≤ p ≤ m)는 그 고양이가 멈추길 원하는 화분 번호, k(1 ≤ k ≤ m)는 그 고양이가 좋아하는 개박하 종류의 수이다. 이어서 k개의 서로 다른 정수가 주어지며, 이는 고양이가 좋아하는 식물 번호이다.

모든 테스트 케이스에 대해 n의 합은 2 \cdot 10^5, m의 합은 2 \cdot 10^5, 모든 k의 합은 5 \cdot 10^5 이하이다.


出力

각 테스트 케이스마다, 위 조건을 만족하도록 개박하 식물을 배치할 수 있으면 yes, 그렇지 않으면 no를 출력한다.


例題 

2
3 5
2 2 1 5
2 3 1 4 5
4 2 3 4
3 5
2 2 1 5
2 3 1 4 5
5 2 3 4
yes
no

出典

ICPC World Finals 2025 F

ログインしないとコードを書けません。