33591번 - Dating 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 2048 MB | 47 | 19 | 13 | 43.333% |
문제
You are the developer of a dating app which ignores gender completely. The app has $n$ users, indexed from $1$ to $n$. Each user’s profile features a list of the activities they enjoy doing. There are $m$ possible activities, indexed from $1$ to $m$.
A match between two users is good if they share at least one activity and, at the same time, both of them like at least one activity that the other user does not like.
Find a good match if it exists.
입력
The first line contains two integers $n$ and $m$ ($2 ≤ n ≤ 200\, 000$, $1 ≤ m ≤ 10^6$) — the number of users and the number of activities.
Each of the following $n$ lines contains a number $k_i$ ($0 ≤ k_i ≤ m$) — the number of activities that user $i$ likes — followed by $k_i$ distinct integers from $1$ to $m$ — the activities user $i$ likes.
It is guaranteed that $k_1 + k_2 + \cdots + k_n$ does not exceed $10^6$.
출력
Print YES if a good match exists. Otherwise, print NO.
If a good match exists, on the next line print two integers — the indexes of two users that make a match.
예제 입력 1
3 5 3 1 2 4 5 1 2 3 4 5 2 1 5
예제 출력 1
YES 3 1
Users $1$ and $3$ form a match, because they share activity $1$, and, furthermore, user $3$ likes activity $5$ (which user $1$ does not like) and user $1$ likes activity $4$ (which user $3$ does not like). Note that users $1$ and $2$, as well as users $2$ and $3$, do not form a match, as there is no activity that users $1$ or $3$ like, and user $2$ doesn’t like.
예제 입력 2
3 3 1 1 1 2 3 2 3 1
예제 출력 2
NO