本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn

1358. Improve SPAM


Description

After the amazing job you did cleaning up duplicate users from the client database, your boss is eager to be impressed by your improvements to the company SPAM (System for Publishing Amazing Marketing).

Despite the marketing campaigns being extremely useful for clients, some complaints were received by the customer service indicating that too many messages are being sent, and that certain clients even receive the same message multiple times.

SPAM is based on mailing lists. Each mailing list is composed of client emails and/or other mailing lists. Client emails might be added to existing mailing lists at any point in time, while only when a mailing list is created it can be added to any number of existing mailing lists. Notice that it is not possible to create several mailing lists at the same time. 

When a message is sent to a mailing list, the system sends the message to each address in the list. If the address in the list is a client email, then the message is sent to that client email; if instead the address is a mailing list, then the process is started for that mailing list.

Due to privacy reasons, in the following example mailing lists and client emails are represented by integers. Suppose that 1, 2 and 3 are mailing lists, while 4 and 5 are client emails. Moreover, mailing list 1 contains mailing lists 2 and 3, mailing list 2 contains client emails 4 and 5, while mailing list 3 contains client email 4 and mailing list 2. Now suppose that a message is sent to mailing list 1. This means that the list is processed as described above, and then mailing lists 2 and 3 are also processed. When mailing list 2 is processed, the message is sent to client emails 4 and 5. When mailing list 3 is processed, a second message is sent to client email 4, and mailing list 2 is processed again, which yields a third message sent to client email 4 and a second message sent to client email 5. Thus, a total of  ve messages are sent to client emails.

Your task is to optimize SPAM in such a way that no client receives the same message multiple times. As a  rst step, your boss wants to know the number of messages sent before and after your improvements. In the above example, just two messages should be sent to client emails after your work is done.

Input

The  first line contains two integers \$N\$ and \$L (2 \leq N \leq 2000, 1 \leq L \leq min(N - 1, 1000))\$, representing respectively the number of addresses in the system, and the number of addressess that are mailing lists. Addresses are identified by distinct integers from 1 to \$N\$. Addressessfrom 1 to \$L\$ are mailing lists, while the rest are client emails. For \$i = 1, 2,\ldots, L\$ the \$i\$-th of the next \$L\$ lines describes mailing list \$i\$ with an integer \$K (1 \leq K < N)\$ followed by \$K\$ different integers \$M_1, M_2,\ldots M_K (1 \leq M_i \leq N \$ for \$i = 1, 2,\ldots, K)\$, indicating that the mailing listtcontains the \$K\$ addresses \$M_1, M_2,\ldots, M_K\$. Each client address appears in at least one mailing  list.

Output

Output a single line with two integers \$B\$ and \$A\$ indicating respectively the number of messages sent to client emails before and after your improvements, if a message is sent to mailing list 1. Because these numbers can be very large, output the remainder of dividing them by \$10^9 + 7\$.

Samples

Input Copy
5 3
2 2 3
2 4 5
2 4 2
Output
5 2
Input Copy
15 6
1 6
7 10 11 12 13 9 7 8
5 6 14 4 5 15
2 14 15
2 4 14
2 5 4
Output
5 2
Input Copy
10 5
4 8 9 10 3
3 9 10 6
3 8 9 7
6 2 3 6 7 8 10
5 9 10 3 1 7
Output
6 4

Source

ICPC Latin American Regional 2019
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 256MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1039. ICPC Latin American Regional 2019
My history solutions

You didn't submit any solution!
Submit your solution

Login Register