인경강

시간 제한2초메모리 제한1024 MB

요약

각 열의 물 칸이 압축된 형태로 주어질 때, 1번 열에서 M번 열까지 위, 아래, 오른쪽으로 물길이 이어지는지 판별합니다.

난이도: 보통10점 중 5점
유형: 구간, 투 포인터, 구현
정답자: 아직 제출이 없습니다

문제

평생을 시골에서 보낸 시은이는 첫 서울 여행에서 한강을 보고 크게 감동받았다. 그 감동을 INPC 참가자들에게도 전하려고, 대회가 진행되는 동안 인하대학교에 한강처럼 생긴 강을 만들기로 했다. 이 강의 이름은 인경강이다.



인경강을 만들 수 있는 예

인경강을 만들 수 없는 예

인하대학교의 부지는 직사각형이며, $N$ 행 $M$ 열의 정사각형 칸으로 나뉜다. 1행이 가장 위이고 1열이 가장 왼쪽이다. 각 칸은 땅 또는 물이다. 다음 조건을 모두 만족하면 인경강을 만들 수 있다. 특히 마지막 조건에서는 왼쪽으로 이동할 수 없다는 점에 유의하라.

1번 열에 물이 한 칸 이상 있다.
$M$ 번 열에 물이 한 칸 이상 있다.
1번 열의 물 가운데 어떤 물(적어도 하나)에서 출발하면, 위, 아래, 오른쪽으로 인접한 물을 따라 0번 이상 이동해 $M$ 번 열의 물에 도달할 수 있다.

입력으로 1열부터 $M$ 열까지 $M$ 개의 열 정보가 주어진다. 열 정보는 각 열에 물이 어떻게 분포하는지 나타내는 길이가 짝수인 수열이다. 수열은 빈 수열에서 시작해, 다음 과정을 순서대로 수행하여 만들어진다. 열에 물이 하나도 없는 경우는 주어지지 않는다.

수열이 비어 있다면 가장 위에 있는 물의 행 번호를, 그렇지 않다면 행 번호가 수열의 마지막 수보다 큰 물 가운데 가장 위에 있는 물의 행 번호를 수열의 맨 뒤에 추가한다.
행 번호가 수열의 마지막 수인 물에서 출발해, 아래로 인접한 물을 따라 0번 이상 이동해 도달할 수 있는 물 가운데 행 번호가 가장 큰 물을 수열의 맨 뒤에 추가한다.
행 번호가 수열의 마지막 수보다 큰 물이 있다면 1번 과정으로 돌아가고, 없다면 열 정보가 완성되었으므로 마친다.

인하대학교 부지의 크기와 $M$ 개의 열 정보가 주어졌을 때, 인경강을 만들 수 있는지 판별하라.

입력

첫째 줄에 인하대학교 부지의 크기 $N$ 과 $M$ 이 공백으로 구분되어 주어진다.

둘째 줄에 1열, 2열, …, $M$ 열의 열 정보 길이를 나타내는 $M$ 개의 정수가 공백으로 구분되어 주어진다.

다음 $M$ 개의 줄에 걸쳐 $M$ 개의 열 정보가 열의 오름차순으로 주어진다. 각 열 정보의 수들은 공백으로 구분되어 주어진다.

출력

인경강을 만들 수 있다면 YES, 아니라면 NO를 출력한다.

제한

$1 \le N \le 1{,}000{,}000{,}000$
$1 \le M \le 100{,}000$
$2 \le$ 열 정보의 길이 $\le 20$

예제5

예제 1

입력

8 10
2 4 2 2 2 2 4 4 4 2
4 4
2 2 4 5
5 5
4 5
3 4
3 6
2 4 6 6
2 2 4 6
2 2 5 5
4 7

예상 출력

YES

예제 2
입력
```
5 5
2 2 2 2 2
1 5
1 5
1 5
1 5
1 5
```
예상 출력
```
YES
```
예제 3
입력
```
10 3
4 4 2
3 4 8 9
3 4 8 9
7 8
```
예상 출력
```
YES
```
예제 4
입력
```
5 4
2 4 4 2
1 1
1 1 3 5
1 3 5 5
4 5
```
예상 출력
```
NO
```

예제 5

입력

2000 5
2 4 8 4 2
1 1999
1 1 1999 1999
1 1 134 135 1279 1947 1999 1999
2 2 2000 2000
2 2000

예상 출력

NO