블록 다루기
면접 대비시간 제한1초메모리 제한1024 MB
서로 다른 번호와 색을 가진 N개의 블록이 주어지고, 같은 색 블록끼리만 교환할 수 있을 때 번호 순으로 정렬할 수 있는지 판별한다.
문제
친구가 게임을 하나 만들었는데, 네가 풀 수 있을지 없을지 알고 싶어 한다.
친구는 N개의 블록을 일렬로 늘어놓았다. 각 블록에는 숫자가 새겨져 있고 색이 칠해져 있다. 모든 숫자는 서로 다르고 1과 N 사이이며, 서로 다른 블록이 같은 색일 수 있다.
게임은 다음과 같이 진행된다. 원하는 만큼 턴을 진행할 수 있다. 한 턴에는 같은 색인 서로 다른 두 블록을 골라 자리를 바꾼다.
블록에 새겨진 숫자를 기준으로 전체 수열을 오름차순으로 정렬할 수 있는지 판별해야 한다.
입력
첫째 줄에 두 정수 N과 K가 주어진다 (1 ≤ N ≤ 105, 1 ≤ K ≤ N). N은 수열에 있는 블록의 수, K는 서로 다른 색의 수이다.
다음 N개의 줄에는 각각 두 정수 ni와 ci가 주어진다 (1 ≤ ni ≤ N, 1 ≤ ci ≤ K). 각각 i번째 블록에 새겨진 숫자와 색이다.
출력
한 줄에 문자 하나를 출력한다. 수열을 오름차순으로 정렬할 수 있으면 대문자 ‘Y’를, 아니면 대문자 ‘N’을 출력한다.