TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

88.7% (188/212)

Submission's AC Ratio

25.6% (277/1080)

Tags

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$)

Output Format

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

Sample Input 1

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 1

3
3
1
3

Hints

Problem Source

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

Subtasks

No. Testdata Range Constraints Score
1 0~2 $t,m\leq 10$ 30
2 3~4 $m\leq 100$ 30
3 5~6 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 2
4 1000 65536 262144 2
5 1000 65536 262144 3
6 1000 65536 262144 3