{"raw_statement":[{"iden":"statement","content":"Aryo has got a lot of intervals for his 2418th birthday. He is really excited and decided to color all these intervals with some colors. He has a simple rule for himself. He calls a coloring nice if there exists no three intervals _a_, _b_ and _c_ such that the following conditions are satisfied simultaneously:\n\n*   _a_, _b_ and _c_ are colored with the same color,\n*   ,\n*   ,\n*   .\n\nMoreover he found out that for every intervals _i_ and _j_, there is at least one point in _i_ which isn't in _j_.\n\nGiven some set of intervals. You have to find the minimum number _k_, such that Aryo can find a nice coloring with _k_ colors."},{"iden":"input","content":"The first line contains a single integer _n_ (1 ≤ _n_ ≤ 103), number of intervals.\n\nThe following _n_ lines contain a interval description each. Each interval is described by two numbers _s__i_, _e__i_ which are the start and end points of it ( - 105 < _s__i_, _e__i_ < 105, _s__i_ ≤ _e__i_). See samples for clarity. A square bracket stands for including of the corresponding endpoint, while a round bracket stands for excluding."},{"iden":"output","content":"Write a single integer _k_ — the minimum number of colors needed for a nice coloring."},{"iden":"examples","content":"Input\n\n2\n\\[1,2)\n(3,4\\]\n\nOutput\n\n1\n\nInput\n\n3\n\\[1,3\\]\n\\[2,6\\]\n(5,7)\n\nOutput\n\n2"}],"translated_statement":[{"iden":"statement","content":"Aryo 在他第 #cf_span[2418] 个生日时得到了很多区间。他非常兴奋，决定用一些颜色给所有这些区间着色。他为自己设定了一个简单的规则：他称一种着色是“好的”，当且仅当存在三个区间 #cf_span[a, b] 和 #cf_span[c]，使得以下条件同时成立：\n\n此外，他发现对于任意两个区间 #cf_span[i] 和 #cf_span[j]，都至少存在一个点属于 #cf_span[i] 但不属于 #cf_span[j]。\n\n给定一组区间，你需要找出最小的 #cf_span[k]，使得 Aryo 能够用 #cf_span[k] 种颜色实现一种“好的”着色。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 103])，表示区间的数量。\n\n接下来的 #cf_span[n] 行每行描述一个区间。每个区间由两个数 #cf_span[si, ei] 描述，分别表示其起点和终点 (#cf_span[ - 105 < si, ei < 105]，#cf_span[si ≤ ei])。具体细节见样例。方括号表示包含对应端点，圆括号表示不包含。\n\n输出一个整数 #cf_span[k] —— 实现“好的”着色所需的最少颜色数。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 103])，表示区间的数量。接下来的 #cf_span[n] 行每行描述一个区间。每个区间由两个数 #cf_span[si, ei] 描述，分别表示其起点和终点 (#cf_span[ - 105 < si, ei < 105]，#cf_span[si ≤ ei])。具体细节见样例。方括号表示包含对应端点，圆括号表示不包含。"},{"iden":"output","content":"输出一个整数 #cf_span[k] —— 实现“好的”着色所需的最少颜色数。"},{"iden":"examples","content":"输入\n2\n[1,2)\n(3,4]\n输出\n1\n\n输入\n3\n[1,3]\n[2,6]\n(5,7)\n输出\n2"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of intervals.  \nLet $ \\mathcal{I} = \\{I_1, I_2, \\dots, I_n\\} $, where each $ I_i = [s_i, e_i] $ or $ (s_i, e_i) $ or $ [s_i, e_i) $ or $ (s_i, e_i] $ is a real interval with $ s_i, e_i \\in \\mathbb{R} $, $ s_i \\leq e_i $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^3 $  \n2. $ -10^5 < s_i, e_i < 10^5 $ for all $ i $  \n3. For every pair $ i \\neq j $, $ I_i \\not\\subseteq I_j $ and $ I_j \\not\\subseteq I_i $ (i.e., no interval is completely contained in another).\n\n**Objective**  \nFind the minimum integer $ k $ such that there exists a coloring $ c: \\mathcal{I} \\to \\{1, 2, \\dots, k\\} $ satisfying:  \nThere exist three intervals $ I_a, I_b, I_c \\in \\mathcal{I} $ with $ c(I_a) = c(I_b) = c(I_c) $, and  \n$$\nI_a \\cap I_b \\neq \\emptyset, \\quad I_b \\cap I_c \\neq \\emptyset, \\quad I_a \\cap I_c = \\emptyset.\n$$  \nThat is, the coloring is “nice” if some color class contains three intervals forming a “chain” with a gap: overlapping consecutively but not all three pairwise.","simple_statement":null,"has_page_source":false}