重排九宫是一个古老的单人智力游戏。据说重排九宫起源于我国古时由三国演义故事“关羽义释曹操”而设计的智力玩具“华容道”，后来流传到欧洲，将人物变成数字。原始的重排九宫问题是这样的：将数字1～8按照任意次序排在3*3 的方格阵列中，留下一个空格。与空格相邻的数字，允许从上，下，左，右方向移动到空格中。游戏的最终目标是通过合法移动，将数字1～8 按行排好序。最长距离问题考察的是，从数字1～8 在3*3的方格阵列的初始排列A出发，找出与其相应的最长距离目标状态B。换句话说，从A到B的最优移动序列的长度最长。

图6-10 最长距离问题

对于给定的3*3 方格阵列中数字1～8 初始排列，计算与初始排列相应的最长距离目标状态。

输入数据有3 行，每行有3 个数字表示该行方格中的数字，0 表示空格。

输出第1 行有2个正整数x 和y，x 是最长距离的值，y是最长距离目标状态个数。从第2行开始，依次输出最长距离目标状态和到达该最长距离目标状态的最优移动序列。用大写英文字母D，U，L，R 分别表示向下，向上，向左，向右移动。