H. Hop on all the Double-Deckers!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On the streets of Hong Kong, double-decker buses are everywhere, serving passengers like you and me at every moment! If you observe them closely, you'll notice that these double-deckers differ in appearance, length, engine sound, and more. This is because they are in different models, and you have been challenged to hop on every model available in the district!

There are $$$N$$$ bus stops, numbered from $$$1$$$ through $$$N$$$. Connecting these bus stops, there are $$$M$$$ bus routes, numbered from $$$1$$$ through $$$M$$$. The $$$i$$$-th route has $$$C_i$$$ unique stops in a specific order and runs bidirectionally. Travelling between two adjacent stops on any route always takes exactly 1 minute. Because buses run very frequently, you can assume that every minute, there is at least one bus at each stop for each direction of every route.

The bus company owns $$$K$$$ distinct double-decker models, numbered from $$$1$$$ through $$$K$$$. The $$$i$$$-th route is assigned to a specific model $$$D_i$$$, and the route is served by that model only.

You start at stop 1 with at most $$$T$$$ minutes. Your goal is to:

  • Ride on each of the $$$K$$$ models at least once (i.e., spend at least 1 minute travelling on a route served by that model).
  • Return to stop 1 in no more than $$$T$$$ minutes.

Switching from one bus to another at any stop requires no time, and you can always board a bus immediately without waiting. Are you able to complete the challenge?

Input

The first line contains four integers: $$$N$$$, $$$M$$$, $$$K$$$, and $$$T$$$ ($$$2 \leq N, T \leq 100$$$, $$$1 \leq M \leq 20$$$, $$$1 \leq K \leq 10$$$).

The next $$$M$$$ lines each describe a bus route. For the $$$i$$$-th line:

  • The line begins with two integers $$$C_i$$$ and $$$D_i$$$: $$$C_i$$$ is the number of stops on this route ($$$2 \leq C_i \leq 20$$$), and $$$D_i$$$ is the model number for this route ($$$1 \leq D_i \leq K$$$).
  • This is followed by $$$C_i$$$ integers: $$$S_{i1}, S_{i2}, \ldots, S_{iC_i}$$$, where $$$S_{ij}$$$ is the $$$j$$$-th stop of route $$$i$$$ ($$$1 \leq S_{ij} \leq N$$$).

It is guaranteed that you can travel to every stop from stop 1 and that every model is assigned to at least one route.

Output

If it is possible to hop on all different double-deckers models and be backed at stop 1 on or before $$$T$$$, output a single line Yes, otherwise a single line No.

Examples
Input
4 2 2 3
3 1 1 2 3
3 2 1 2 4
Output
Yes
Input
3 2 2 3
2 1 1 2
2 2 3 1
Output
No
Note

Sample 1:

A valid plan is as follows:

  • Travel from stop 1 to stop 2 via route 1, with model 1.
  • Then, travel from stop 2 back to stop 1 via route 2, with model 2.

You have used both models (1 and 2) and returned to stop 1 in 2 minutes, which does not exceed $$$T=3$$$. Because buses are always available, you do not have to wait for the next bus at any stop.