本文中所给出的题面为原题面的中文翻译,并非原始题面。翻译如有错误之处,请联系指出。

奶牛就是这么挑食。每头奶牛都有自己喜欢的食物和饮料,她不会吃她不喜欢的食物和或者喝她不喜欢的饮料。

农夫约翰为他的奶牛做了美味的饭菜,但他忘记根据她们的喜好检查他的菜单。虽然他可能无法让每头奶牛都吃饱,但他想让尽可能多的奶牛吃一顿符合她们喜好的饭。

农夫约翰烹制了 FFF 种食物并准备了 DDD 种饮料。他的 NNN 头奶牛中的每一头都给出了她喜欢吃的食物种类和饮料种类。农夫约翰必须为每头奶牛分配一种食物类型和一种饮料类型,以最大限度地增加同时获得这两种食物的奶牛数量。

每道菜或饮料只能由一头牛食用(即一旦将种类编号为 222 的食物分配给一头牛,就不能再将这种食物分配给其他牛)。

接下来有 NNN 行数据。第 iii 行以两个整数 FiDiF_i D_iFi​Di​ 开头,即奶牛喜欢吃的食物种类的数量和喜欢喝的饮料种类的数量。之后有 FiF_iFi​ 个整数给出了第 iii 头奶牛喜欢吃的菜的编号,有 DiD_iDi​ 个整数给出了第 iii 头奶牛喜欢喝的饮料种类的编号。

一行一个整数,表示可以享受到自己喜欢的食物和饮料的奶牛的最大数量。

本题的难点主要在于建图。

一种很容易想到的做法是建立一个超级源点连接食物,食物连牛,牛连饮料,饮料连接超级汇点,然后再跑一遍最大流。但这个算法是错误的,它可能会重复选择同一只奶牛。

那么可以运用拆点的思想,将一只奶牛拆成两个点,食物连入点,出点连饮料,就避免了重复选择的问题。