402363: GYM100738 I Lazy mobile users

Informikas is creating a website. He has gathered a great amount of information, come up with a beautiful design and optimized the page for best user experience.

To make the structure of the webpage simple, Informikas abides to simple rules:

• every page has zero or more links;
• no page has a link to the homepage;
• there are no two pages who are linking to the same page;
• a page cannot link to itself;
• when starting from the homepage, you can reach every other page on the site.

However, not everything is flawless. After showing his website to friends he have found out that people, who browse the Internet on their mobile phones, are very lazy:

• they hate to input website address by hand, so they store the homepage address in the bookmarks. That means they always enter the site through homepage and never through some internal page;
• for browsing they only use back button and links displayed on the pages;
• they get easily annoyed when they open the same page (either by clicking link or clicking "back" button) for some specific number of times. And when they get annoyed, they just immediately close the browser.

Links and "back" button works as in every browser:

• pressing the link will load a page that is linked;
• pressing the "back" button causes browser to open the page from which user came to the current page.

Informikas would like to know, what is the maximum number of pages a mobile user could view before getting annoyed. Having the list of webpages with links inside them and the count of times a user has to see the same page to get annoyed, find that number.

In the first line of input there are two integers N and K (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10⁵) – the number of webpages and the number of times mobile user could see the same page before getting annoyed. The pages are numbered from 1 to N. Every following N lines consist of integer M_i (0 ≤ M_i, 1 ≤ i ≤ N) – the number of links inside the page i – followed by M_i integers Q_i, j (1 ≤ Q_i, j ≤ N,) – the names of pages, meaning that page i has a link to page Q_i, j.

The homepage (the page mobile user starts browsing the website) has the index 1 (the page described on the second line of input).

Output single integer, equal to the maximum number of pages mobile user could see before getting annoyed.

3 1
2 2 3
0
0

2

3 2
2 2 3
0
0

3

8 2
3 2 3 4
2 5 7
0
0
1 6
0
1 8
0

7

In the first test case, user enters the home page and then clicks a link to one of the other two pages (either 2 or 3). Any of the two pages have no links. Now, by pressing "back" button, mobile user would reopen homepage, get annoyed and leave. This gives an answer of 2.

In the second test case mobile user could go 1 > 2 < 1 > 3 (here > means clicking the link and < means pressing back button). This results in 3 viewed pages.

In the third test case one of possible paths would be 1 > 3 < 1 > 2 > 5 > 6 < 5 < 2 > 7 > 8. This results in 7 viewed pages (1, 2, 3, 5, 6, 7, 8).