Travel Plan

Interview

Time limit2sMemory limit128 MB

Summary

Given an adjacency matrix of cities, decide if consecutive cities in a given visit order all lie in the same connected component.

Level: Easy3 of 10
Topics: Union-find, Graph, BFS
Solved: No attempts yet

Problem

Donghyuk wants to visit several cities with his friends in a fixed order. There are N cities in Korea, and some pairs of cities are connected by bidirectional roads. Even when two cities do not have a direct road, they can still be consecutive in the travel route if it is possible to move between them through other cities.

Determine whether the given sequence of cities can be visited in order. Visiting the same city multiple times is allowed.

Input

The first line contains the number of cities N. N is at most 200.

The second line contains the number of cities M in the travel plan. M is at most 1000.

Each of the next N lines contains N integers describing the adjacency matrix. In the i-th line, the j-th value is 1 if city i and city j are connected, and 0 otherwise. Connections are bidirectional.

The last line contains M city numbers in the order of the travel plan. Cities are numbered from 1 to N.

Output

Print YES on one line if the travel plan is possible; otherwise, print NO.

Examples1

Example 1
Input
```
3
3
0 1 0
1 0 1
0 1 0
1 2 3
```
Expected output
```
YES
```