编程介的小学生 2019-10-04 17:57 采纳率: 20.5%
浏览 90

Vase collection

Description

Mr Cheng is a collector of old Chinese porcelain, more specifically late 15th century Feng dynasty vases. The art of vase-making at this time followed very strict artistic rules. There was a limited number of accepted styles, each defined by its shape and decoration. More specifically, there were 36 vase shapes and 36 different patterns of decoration - in all 1296 different styles.
For a collector, the obvious goal is to own a sample of each of the 1296 styles. Mr Cheng however,like so many other collectors, could never afford a complete collection, and instead concentrates on some shapes and some decorations. As symmetry between shape and decoration was one of the main aestheathical paradigms of the Feng dynasty, Mr Cheng wants to have a full collection of all combinations of k shapes and k decorations, for as large a k as possible. However, he has discovered that determining this k for a given collection is not always trivial. This means that his collection might actually be better than he thinks. Can you help him?
Input

On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer m <= 100, the number of vases in the collection. Then follow m lines, one per vase, each with a pair of numbers, si and di, separated by a single space, where si ( 0 < si <= 36 ) indicates the shape of Mr Cheng's i:th vase, and di ( 0 < di <= 36 ) indicates its decoration.
Output

For each test scenario, output one line containing the maximum k, such that there are k shapes and k decorations for which Mr Cheng's collection contains all k*k combined styles.
Sample Input

2
5
11 13
23 5
17 36
11 5
23 13
2
23 15
15 23
Sample Output

2
1

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥20 thinkphp适配人大金仓问题
    • ¥15 有卷积神经网络识别害虫的项目吗
    • ¥15 数据库数据成问号了,前台查询正常,数据库查询是?号
    • ¥15 算法使用了tf-idf,用手肘图确定k值确定不了,第四轮廓系数又太小才有0.006088746097507285,如何解决?(相关搜索:数据处理)
    • ¥15 彩灯控制电路,会的加我QQ1482956179
    • ¥200 相机拍直接转存到电脑上 立拍立穿无线局域网传
    • ¥15 (关键词-电路设计)
    • ¥15 如何解决MIPS计算是否溢出
    • ¥15 vue中我代理了iframe,iframe却走的是路由,没有显示该显示的网站,这个该如何处理
    • ¥15 操作系统相关算法中while();的含义