Chef Shifu and Celebration

Nguồn: https://www.codechef.com/

Chef Shifu wanted to celebrate the success of his new restaurant with all his employees. He was willing to host a party and he had decided the location of the party as well. However, Chef Shifu was a shy person and wanted to communicate with the least possible employees to inform them about the party, and that these employees could inform their friends.
Note that an employee could only inform his/her immediate friends about the party, not his/her friends’ friends.
Chef Shifu has a list of all the friendships among his employees. Help him find the minimum number of employees he should inform, so that every employee knows about the celebration party.

Input

First line contains a single integer T - the total number of testcases.

T testcases follow. For each testcase:

The first line contains 2 space-separated integers N and M - the total number of employees working under Chef Shifu and the number of friendship relations.

M lines follow - each line contains 2 space-separated integers u and v, indicating that employee u is a friend of employee v and vice-versa.

The employees are numbered from 1 to N, and each employee is assigned a distinct integer.

Output

For each testcase, print the minimum number of employees to be informed on a new line.

Constraints

Subtask 1: 5 points

1 ≤ T ≤ 5

1 ≤ N ≤ 4

0 ≤ M ≤ N*(N-1)/2

Subtask 2: 35 points

1 ≤ T ≤ 5

1 ≤ N ≤ 15

0 ≤ M ≤ N*(N-1)/2

Subtask 3: 60 points

1 ≤ T ≤ 5

1 ≤ N ≤ 20

0 ≤ M ≤ N*(N-1)/2

Example

Input

2

3 3

1 2

2 3

1 3

4 3

1 2

2 3

3 4

Output

1

2

Explanation

In testcase 1, since every employee is a friend of every other employee, we just need to select 1 employee.

In testcase 2, selecting employees 2 and 4 would ensure that all 4 employees are represented.

Similarly, selecting employees 1 and 3 would also ensure that all 4 employees are selected.

In both cases, we must select 2 employees in the best case.

Rupsa and the Game

Nguồn: https://www.codechef.com

Công chúa Rupsa thấy một người bạn đang chơi một trò chơi đặc biệt. Trò chơi diễn ra như sau:

^·          N+1 số xuất hiện tuần tự ( mỗi số tại một thời điểm ) từ A0 đến AN.

^·          Bạn phải ghi những con số vào một tờ giấy, A0 được viết đầu tiên. Những số khác được viết theo quy tắc quy nạp – Sau khi Ai-1 số đã được ghi trong một hàng, thì Ai có thể được viết ở hai đầu của hàng. Nghĩa là, bạn viết A0 đầu tiên, sau đó A1 có thể được viết ở bên trái hoặc bên phải để tạo thành A0A1 hoặc A1A0, và cứ tiếp tục như vậy.

^·          Ai phải được viết trước Aj, với mọi i < j.

^·          Ở bước bạn viết số Ai (i>0), điểm số của bạn sẽ được tăng lên một lượng bằng tích của Ai và số cạnh nó. (Chú ý rằng ở bất cứ bước nào thì chỉ có một số duy nhất cạnh nó giống như bạn viết số cuối cùng).

^·          Tổng số điểm của trò chơi là số điểm bạn có được sau khi viết tất cả N + 1 số.

^·          Công chúa Rupsa muốn tìm ra tổng số điểm của tất cả các cách chơi khác nhau. Hai cách chơi khác nhau nếu sau khi viết N + 1 số, chúng ta đọc từ trái sáng phải, sẽ xuất hiện những vị trí i mà số ở vị trí i của 2 cách chơi khác nhau. Nhưng bởi vì công chúa đã tìm ra tình yêu đích thực của mình, một hoàng tử ếch, và rất nóng lòng gặp hoàng tử, bạn hãy giúp công chúa giải quyết nó càng sớm càng tốt. Bởi kết quả có thể rất lớn nên chỉ cần in kết quả lấy dư cho 10⁹ + 7.

Dữ liệu vào:

+ Dòng đầu tiên chứa một số tự nhiên T, thể hiện số lượng test.

+ Dòng đầu của mỗi test chứa 1 số tự nhiên N.

+ Dòng thứ hai chứa N + 1 số tự nhiên từ A0 đến AN

Dữ liệu ra:

+ Với mỗi test, in ra một dòng chứa một số là kết quả tìm được

Ràng buộc:

+ 1 ≤ T ≤ 10

+ 1 ≤ N ≤ 10⁵

+ 1 ≤ Ai ≤ 10⁹

Subtasks

Subtask #1: 1 ≤ N ≤ 10 (10 điểm)

Subtask #2: 1 ≤ N ≤ 1000 (20 điểm)

Subtask #3: Như ràng buộc gốc (70 điểm)

Ví dụ:

Input:

1

1

1 2

Output:

4

Giải thích: Có 2 cách chơi: A0A1 có số điểm là 2 và A1A0 cũng có số điểm là 2. Do đó đáp án là 2+2= 4

XỔ SỐ ĐIỆN TOÁN

Có N người (đánh số từ 1 đến N) tham gia một đợt xổ số điện toán. Mỗi người nhận được một thẻ gồm M ô (đánh số từ 1 đến M). Người chơi được chọn K ô trong số các ô đã cho bằng cách đánh dấu các ô được chọn. Sau đó các thẻ này được đưa vào máy tính để xử lý.

Máy tính chọn ra K ô ngẫu nhiên (gọi là các ô kết quả) và chấm điểm từng thẻ dựa vào kết quả đã sinh. Cứ mỗi ô chọn đúng với ô kết quả thì thẻ chơi được tính 1 điểm. Giả thiết biết các ô chọn cũng như các điểm tương ứng của từng thẻ chơi, hãy xác định tất cả các kết quả có thể có mà máy sinh ra.

Dữ liệu vào: đọc từ file vănbản XOSO.INP gồm:

- Dòng đầu ghi các số N, M, K

- Dòng thứ i trongN dòng tiếp ghi thẻ chơi của người i gồm K+1 số: K số đầu là các số hiệu của các ô chọn, cuối cùng là điểm tương ứng.

Kết quả ra: ghi vào tệp văn bản XOSO.OUT, mỗi dòng là một kết quả gồm K số ghi số hiệu các ô mà máy đã sinh.

Ghi chú:

- Các số trên cùng mộtdòng trong các file vào/ ra, được ghi cách nhau ít nhất một dấu trắng.

- Giới hạn kích thước:N ≤ 100, M ≤50, K ≤10.

- Dữ liệu vào trong các test là hợp lệ và đảm bảo có ít nhất một đáp án. 

Ví dụ: 

XOSO.INP	XOSO.OUT
5 9 4 2 4 6 8 2 5 6 8 9 0 2 4 5 6 2 1 2 3 7 3 3 5 6 9 1	1 2 3 4 2 3 4 7

CUNG ĐIỆN

Nguồn: Olympic miền Nam-2011

Ở một vương quốc nọ có 1 vị vua và ông có N quý phi. Trên miếng đất hình vuông có kích thước NxN, nhà vua muốn xây dựng cho mỗi quý phi, mỗi người một cung điện (giả sử mỗi cung điện đều nằm trên một mảnh đất kích thước 1x1). Vấn đề là các quý phi này có tính ghen ghét nhau nên nhà vua không muốn các cung điện nhìn thấy nhau từ các hướng (ngang, dọc, chéo).Chi phí xây dựng các cung điện trên mỗi ô đất có thể có giá thành khác nhau. Nhà vua muốn xây dựng N cung điện với tổng chi phí thấp nhất.

Yêu cầu: Bạn hãy giúp nhà vua thực hiện công việc đó

Dữ liệu vào: Từ file văn bản CUNGDIEN.INP gồm N+1 dòng

- Dòng đầu chứa số N (1≤N≤16)

- N dòng sau, mỗi dòng chứa N số là chi phí xây dựng tại ô đất tương ứng (Chi phí xây dựng cung điện trong một ô có giá trị nguyên từ 1 đến 100). Mỗi số cách nhau ít nhất một khoảng trắng
Dữ liệu ra: Ghi ra file văn bản CUNGDIEN.OUT gồm một số duy nhất cho biết tổng chỉ phí thấp nhất cho việc xây dựng. Giả sử dữ liệu luôn có lời giải

Ví dụ:

CUNGDIEN.INP	CUNGDIEN.OUT
4 3 4 12 3 6 1 7 1 2 4 1 5 12 3 8 7	15

Giải thích: các ô được chọn là (1,2), (2,4), (3,1), (4,3)

GRID GAME

Nguồn: https://uva.onlinejudge.org

(Đóng góp của Đinh Nguyên Khôi)

Alice và Bob cả hai đều có kẹo nhiều ơi là nhiều ! Nhưng mà tụi nó muốn ăn. Cho nên hai đứa nó quyết định chơi một trò chơi theo lượt như sau:

Tụi nó sẽ điền vào một cái bảng M có kích thước N x N với những số nguyên bất kỳ. Alice sẽ bắt đầu trò chơi bằng cách kẻ ngang những một hàng i mà nó chưa kẻ. Bây giờ tới lượt của Bob, nó phải kẻ dọc cột j mà trước đó nó chưa kẻ. Sau khi lượt của Bob kết thúc, Alice sẽ lấy được số kẹo mà giao ở cột i và hàng j là M(i, j). Nếu như M(i, j) < 0, tức là điều này đồng nghĩa với việc Alice sẽ phải đưa cho Bob M(i, j) viên kẹo. Trò chơi sẽ kết thúc khi toàn bộ các cột và hàng đều được kẻ rồi. (Xem hình để biết thêm chi tiết).

Nhiệm vụ của bạn rất là đơn giản thôi ! Hãy tính xem Alice có thể lấy được nhiều nhất là bao nhiêu viên kẹo, hay nói cách khác, là tính xem Bob lấy được ít nhất bao nhiêu viên. Giả sử hai người này đều chơi tối ưu.

Input: Dòng đầu là số nguyên t (1 <= t <= 20), là số test case trong một test. 
Mỗi test case sẽ bắt đầu bởi một số nguyên N (1≤N≤ 8), là kích thước của cái bảng. 
N dòng sau, mỗi dòng có N số nguyên. Số nguyên thứ j trên dòng thứ i là M(i , j).

Output: Gồm t dòng, dòng thứ i tương ứng với test case thứ i, chỉ in ra một số nguyên duy nhất là số lượng kẹo nhiều nhất mà Alice có thể ăn được.

Ví dụ:

INPUT	OUTPUT
3 2 10 10 -5 -5 2 10 10 -5 -5 2 10 -5 -5 10	5 5 -10