D. Diving Groupmates
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ben and his $$$N$$$ groupmates, numbered from $$$1$$$ to $$$N$$$, are collaborating on a heavy school project that consists of $$$M$$$ tasks, numbered from $$$1$$$ to $$$M$$$. To complete the project efficiently and meet the project deadline, Ben decides to assign the $$$M$$$ tasks to his $$$N$$$ groupmates. For each task $$$i$$$ ($$$1 \leq i \leq M$$$), there is exactly one groupmate who will be the Person-in-Charge $$$PIC_i$$$ ($$$1 \leq PIC_i \leq N$$$), responsible for ensuring the task gets done. Additionally, each task $$$i$$$ has $$$P_i$$$ "peanuters" ("花生友" in Cantonese) — groupmates who prefer to observe the progress and give comments without actively contributing.

To ensure the tasks are completed on time, Ben has to send reminder messages in the group chat, one for each task. The behavior when Ben sends a reminder for task $$$i$$$ is as follows:

  • The Person-in-Charge $$$PIC_i$$$ dives — pretends to be unavailable and ignores the reminder message for task $$$i$$$.
  • All peanuters of task $$$i$$$ upwater — pop online and read all messages currently in the group chat. Note that a groupmate can be both Person-in-Charge of some tasks and peanuters of some other tasks. In this case, once they read the message, they will be forced to handle all tasks for which they are the Person-in-Charge among the tasks mentioned in those messages.

Ben's goal is to maximize the number of tasks that are handled by their respective Person-in-Charge. A task is considered handled if the Person-in-Charge reads the reminder message for that task. To achieve this, Ben can carefully decide the order in which he sends reminders for the $$$M$$$ tasks. Your task is to help Ben determine the optimal order for sending reminders so that the number of tasks handled by their respective Person-in-Charge is maximized.

Input

The first line contains two integers, $$$N$$$ and $$$M$$$, the number of groupmates and the number of tasks respectively. ($$$1 \leq N \leq 10^5$$$, $$$1 \leq M \leq 10^5$$$)

The second line contains $$$M$$$ integers, the $$$i$$$-th integer denotes $$$PIC_i$$$, the Person-in-Charge of task $$$i$$$. ($$$1 \leq PIC_i \leq N$$$)

The next $$$M$$$ lines each start with an integer $$$P_i$$$ specifying the number of peanuters of task $$$i$$$, followed by $$$P_i$$$ distinct integers denoting the peanuters of task $$$i$$$. ($$$0 \leq P_i \leq N - 1$$$, $$$0 \leq \sum_{i=1}^{m} P_i \leq 10^5$$$)

It is guaranteed that the Person-in-Charge will not be a peanuter of the same task.

Output

The output contains a line of $$$M$$$ integers, representing the optimal order to send the reminder messages that maximizes the number of tasks that can be handled. Each task from 1 to M should appear exactly once.

Examples
Input
3 3
1 3 2
1 2
0
1 3
Output
2 3 1
Input
4 5
1 3 4 1 2
2 4 3
0
1 3
1 3
1 4
Output
4 1 2 3 5
Note

Explanation of sample 1:

Consider a project with $$$N = 3$$$ groupmates and $$$M = 3$$$ tasks.

  • Task 1: The Person-in-Charge is groupmate 1 ($$$PIC_1 = 1$$$), and the peanuter is groupmate 2.
  • Task 2: The Person-in-Charge is groupmate 3 ($$$PIC_2 = 3$$$), with no peanuters.
  • Task 3: The Person-in-Charge is groupmate 2 ($$$PIC_3 = 2$$$), and the peanuter is groupmate 3.

Ben sends reminder messages in the order $$$[2, 3, 1]$$$.

  1. Ben sends a reminder for task 2.
  2. Ben sends a reminder for task 3. The peanuter, groupmate 3, reads all messages in the group chat (reminders for tasks 2 and 3), and handles task 2 since groupmate 3 is the Person-in-Charge for task 2 ($$$PIC_2 = 3$$$).
  3. Ben sends a reminder for task 1. The peanuter, groupmate 2, reads all messages in the group chat (reminders for tasks 2, 3, and 1), and handles task 3 since groupmate 2 is the Person-in-Charge for task 3 ($$$PIC_3 = 2$$$).

Thus, 2 tasks are handled, which is the maximum possible.