TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

83.3% (45/54)

Submission's AC Ratio

23.6% (67/284)

Description

俄羅斯娃娃是一種相當特別的木製玩具,通常有數個可以由中間轉開的娃娃,每個娃娃裡面又依序包含數個較小的娃娃。
據說你可以對俄羅斯娃娃許願,而許願的方法是把所有俄羅斯娃娃一一打開排好,默默許下自己的願望,接著威脅其中一隻娃娃,如果沒有實現願望,她這輩子都別想再看到太陽。接著再把俄羅斯娃娃一層一層收疊好,將被威脅的娃娃關在最裡面。所有俄羅斯娃娃會為了要救最裡面的娃娃出來,努力完成你的心願。
聽起來是個有點邪惡的許願方式,但是無論如何艾蜜莉決定一試,既然根據傳說,擁有越多層的俄羅斯娃娃,力量越強大,她決定將她所有蒐藏的俄羅斯娃娃全部展開,看看她可不可以將娃娃重新堆疊,組合出一隻有更多層的俄羅斯娃娃,釋放俄羅斯娃娃的洪荒之力(?
首先,她先測量每個娃娃的寬度和高度,因為她搜集的所有俄羅斯娃娃形狀都相同,所以如果有一個娃娃寬度是$w_1$高度是$h_1$,另外一個娃娃的寬度是$w_2$高度是$h_2$,那麼只要$w_1<w_2$而且$h_1<h_2$,第一個娃娃就可以被放進第二個娃娃中。
請你幫她算算看,根據她所擁有的這些俄羅斯娃娃,她最多可以堆疊出幾層的俄羅斯娃娃。

Input Format

第一列包含一個正整數$t$ ($1\leq t\leq 20$),代表下面的測試資料數量
每筆測試資料前面都包含一個正整數$m$ ($1\leq m\leq 20000$),表示俄羅斯娃娃的數量
緊接著$2m$個正整數$w_1, h_1, w_2, h_2, \dots , w_m, h_m$,其中$w_i$和$h_i$分別表示第$i$個娃娃的寬度和高度 ($1\leq w_i,h_i\leq 1000$)

子任務(測資) 額外限制 分數
1 (0~2) $t,m\leq 10$ 30
2 (3~4) $m\leq 100$ 30
3 (5~6) 40

Output Format

針對每一筆測資,輸出最多可以堆疊出幾層的俄羅斯娃娃

Sample Input

4
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51

Sample Output

3
3
1
3

Hints

Problem Source

建國中學105學年度校隊選拔:初試pE

Subtasks

For Testdata: 0 ~ 2, Score: 30
For Testdata: 3 ~ 4, Score: 30
For Testdata: 5 ~ 6, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536