LQDOJ có \(n\) problem-setter, được đánh số từ \(1\) đến \(n\); có \(m\) tag bài tập trên hệ thống, mỗi người trong \(n\) nhân vật trên đều có một số sở trường bài riêng (như DP, Đồ thị, ...). Hệ thống LQDOJ cũng có một cách phân cấp quản lí các Problem-setter, trong đó người \(x\) có quyền quản lí người \(i\) nếu và chỉ nếu một trong hai điều kiện sau xảy ra:

• Người \(x\) được phân công trực tiếp quản lí người \(i\)
• Người \(x\) có quyền quản lí người \(z\) mà người \(z\) được phân công trực tiếp quản lí người \(i\)

Người mang số \(1\) có quyền quản lí cấp cao nhất và chỉ dưới quyền của Admin Small

Nhân dịp LTPQ giải Nhất VOI và DXMH đạt được cú ăn ba lịch sử, thầy Small yêu cầu \(n\) người tổ chức các contest cho các bạn thí sinh của LQDOJ làm; mỗi người có thể nhờ những người mình quản lí chuẩn bị bài giúp theo các sở trường của họ, mỗi người chỉ ra bài đúng theo sở trường của mình.

Chú ý: Một người có thể ra nhiều bài

Yêu cầu: Với mỗi người, tính số loại bài phân biệt có thể xuất hiện trong contest của người đó; biết mỗi người khi được quản lí của mình nhờ làm bài thì sẽ không bao giờ từ chối

Input

• Dòng đầu tiên chứa hai số nguyên \(n, m (1≤n,m/3≤10^6)\) lần lượt là số Problem-setter và số tag bài có trên LQDOJ
• Dòng thứ \(i\) trong số \(n\) dòng tiếp chứa số nguyên dương \(t_i\) là số loại bài sở trường của người thứ \(i\), theo sau đó là \(t_i\) số nguyên dương phân biệt mô tả các dạng bài sở trường của người \(i\)
• Dòng thứ \(n+2\) chứa \(n−1\) số nguyên \(p_2, p_3, ... , p_n\) \((1≤p_i≤i), p_i\) là người được phân quản lí trực tiếp người \(i\).

Output

• Một dòng duy nhất chứa \(n\) số nguyên là số bài tối đa có thể xuất hiện trong contest của mỗi người

Example

4 3
1 1
2 1 2
1 2
1 3
1 1 3

3 2 2 1

Scoring

Trong mọi test có: \(t_1 + t_2 + ... + t_n <= 10^7\)

• Subtask \(1\): 50% số test ứng với 50% số điểm của bài có \(n, m ≤ 1000\)
• Subtask \(2\): 35% số test ứng với 35% số điểm của bài có \(n ≤ 10^5\)
• Subtask \(3\): 15% số test ứng với 15% số điểm còn lại có \(n ≤ 10^6\)